package com.shr.code_interview;

public class Solution_42 {
    public int FindGreatestSumOfSubArray(int[] array) {
    	int curSum = 0;
    	int maxSum = 0;
    	int maxVal = Integer.MIN_VALUE ;
    	for(int i = 0;i < array.length;i++){
    		curSum += array[i] ;
    		maxVal = Math.max(maxVal, array[i]) ;
    		if(curSum < 0){
    			curSum = 0;
    		}else {
    			maxSum = Math.max(curSum, maxSum) ;
    		}
    	}
    	if(maxVal < 0)
    		return maxVal;
    	else return maxSum ;
    }	
}
